P1850 [NOIP2016] 换教室
P1850 [NOIP2016] 换教室
Meaning
给定一张有 n 个点的无向图且有 n 次事件。我们可以选择其中 m 次事件作为特殊事件,有 pi 的概率从当前点去点 $ b_i $,否则去点 $ a_i $。求期望距离。
CF1216F Wi-Fi
CF1216F Wi-Fi
题意
给定 n,k,和一个长度为 n 的 01 序列 {s}。我们需要把一个长度为 n 空白区间染色,你有如下两种操作:
- 对点 i 单点染色,代价为 i。
- 若点 i 满足 si 为 1,对 [i−k,i+k] 区间染色,代价为 i。
求把空白区间全部染色的最小代价。
CF1324F Maximum White Subtree
CF1324F Maximum White Subtree
题意
给定一棵 n 个结点的树,每个点的颜色是黑白中的一种。对于每个结点 u,选出一棵包含点 u 的连通子树,求其中白点数减去黑点数的最大值。
P4198 楼房重建
P4198 楼房重建
题意
考虑在一个二维平面上,x 轴表示在一条直线上大楼排列的坐标,y 轴表示大楼的高度,那么第 i 栋大楼可以用 (i,hi) 表示。如果第 i 栋大楼与第 j 栋大楼满足 i<j 且 ihi≥jhj,那么第 j 栋大楼被第 i 栋大楼挡住而不可视见。求从 (0,0) 最多能看到的大楼数量。
HISTOGRA - Largest Rectangle in a Histogram
HISTOGRA - Largest Rectangle in a Histogram
悬线法裸题。
题意
从 1 到 n 每个位置有一个高度为 hi,宽度为 1 的矩形。
求所有矩形覆盖面积中最大子矩形。
0%